import scala.actors._
import scala.actors.Actor._

trait MasterWorkerProtocol 
// Master -> Worker
case class StartWorkOn(task: Range) extends MasterWorkerProtocol   // Assign some task to worker
case class StopCurrentTask() extends MasterWorkerProtocol       // Stop doing current task
// Worker/ -> Master
case class TaskDone(time: Long) extends MasterWorkerProtocol	// Report task is done and return result
case class Result(result: Long) extends MasterWorkerProtocol
// Main -> Master
case class KickOut(cmdline: (Long, Long)) extends MasterWorkerProtocol	// Tell master to kick out	
// a range of [from,to)
case class Range (from: Long, to: Long)

class Worker (len: Long) extends Actor {
	val k = len
	def act() {
		react {
			case StartWorkOn(range) =>
				findPerfectSqr(range.from, range.to + 1, sender)
		}
	}
	// this worker will works at range [from, to)
	def findPerfectSqr(from: Long, to: Long, masterRef: OutputChannel[Any]){
		val start = System.currentTimeMillis
		for(i<-from until to){
			var sum:Long = 0
			for(j<-i until i + k){
				sum += j * j
			}
			if(math.sqrt(sum.toDouble)%1 == 0) {
				masterRef ! Result(i)
			}
		}
		masterRef ! TaskDone(System.currentTimeMillis - start) 
	}
}

class Master extends Actor{
	var nOworker: Int = 0
    val alphaDbeta = 500
	var step: Long = 0
	var allWorkers: Array[Worker] = null
	var answer = Long.MaxValue
	var finished = 0
	var cpu: Long = 0
	var real: Long = 0
	
	def act(){
		var start: Long = 0
		while(true) {
			receive {
				case KickOut(cmdline) =>
					start = System.currentTimeMillis
                    decideOptWorkAssignment(cmdline)
					spawn(cmdline)
					kickout(cmdline._1)
				case Result(result) =>
					println(result)
				case TaskDone(time) =>
					reduce(time)
					if(done()){
						real =System.currentTimeMillis-start
						exit()
					}
			}
		}
	}

    def decideOptWorkAssignment(cmdline: (Long, Long)){
        nOworker = math.ceil(cmdline._1/(alphaDbeta*math.sqrt((cmdline._1/cmdline._2)))).toInt
        allWorkers = new Array(nOworker)
    }
	
	def spawn(cmdline: (Long, Long)){
		for(i<-0 until nOworker){
			allWorkers(i) = new Worker(cmdline._2)
			allWorkers(i).start
		}
		if(cmdline._1 % nOworker == 0){
			step = cmdline._1 / nOworker
		} else {
			step = cmdline._1 / nOworker + 1
		}
	}
	def kickout(n: Long){
		var first: Long = 1
		for(i<-0 until allWorkers.length){
			allWorkers(i) ! StartWorkOn(Range(first, math.min(first + step - 1, n))) 
			first += step
		}
	}
	def reduce(time: Long){
		finished += 1
		cpu += time
	}
	def done(): Boolean = {
		return finished == nOworker
	}
} 

object project1 {
    def main(args: Array[String]) {
    	var master = new Master()
    	master.start
    	master ! KickOut((args(0).toLong, args(1).toLong))
    }
}
